
\prob{0019}{最大的质数}

证明：没有最大的质数。
\problabels{yellow/数论, green/证明题}

\subsection{反证法}

基本思路：假设有最大的质数，然后构造一个更大的质数推翻假设。

假设最大的质数为$p_n$，其前面还有$n - 1$个质数$p_1, p_2, \dots, p_{n - 1}$。

将所有质数相乘可得$p_1\cdot p_2\cdot p_3\cdots p_{n - 1}\cdot p_n$，将其加上$1$后可以构造一个数$q$：

\[ q = p_1\cdot p_2\cdot p_3\cdots p_{n - 1}\cdot p_n + 1 \]

但是因为这个数$q$除以所有的质数$p_1, p_2, \dots, p_n$都余$1$，因此数$q$无法被所有的质数整除，所以$q$是一个新的、比$p_n$大的质数，与已知假设“最大的质数为$p_n$”相矛盾。因此，没有最大的质数。

证毕。
